\section{NLP}
\begin{description}
	\item[Question 1] exercise 22.6 (5 points)
	\item[Question 2] exercise 22.8 a and b (5 points)
	\item[Question 3] The IBM Model 3 machine translation model
          assumes that, after the word choice model proposes a list of
          words and the offset proposes possible permutations of the
          words, the language model can choose the best
          permutation. This exercises investigates how sensible that
          assumption is. Try to unscramble the following sentences
          into the correct order yourself and then give an insight on
          how machine can unscramble them. The simpler model you can
          offer, the better. (5 points)
	\begin{itemize}
		\item have programming a seen never I language better
		\item loves john mary
		\item is the communication exchange of intentional
                  information brought by about the production
                  perception of and signs from drawn a of system signs
                  conventional shared
	\end{itemize}
\end{description}

\subsection{Answer 1}
\textbf{22.6} Determine what semantic interpretation would be given to
the following sentences by the grammar of this chapter:

\renewcommand{\labelenumi}{\alph{enumi}.}
\begin{enumerate}
\item It is a wumpus.
\item The wumpus is dead.
\item The wumpus is in 2,2.
\end{enumerate}

Would it be a good idea to have the semantic interpretation for ``It
is a wumpus'' be simly \textit{$\exists x \quad x \in Wumpuses$}?
Consider alternative sentences such as ``It was a wumpus.''

\begin{description}
\item [Answer a] \textit{
  $\exists e$
  $e \in$
  Is(It,[$\exists w$ Wumpus(w)])
  $\wedge$
  During(Now,e)
}
\item [Answer b] \textit{
  $\exists e$
  $e \in$
  Dead([$\exists !w$ Wumpus(w)])
  $\wedge$
  During(Now,e)
}
\item [Answer c] \textit{
  $\exists e$
  $e \in$
  Is([$\exists !e$ Wumpus(w)],x)
  $\wedge$
  In(x,[2,2])
  $\wedge$
  During(Now,e)
}
\end{description}



\subsection{Answer 2}
\textbf{22.8} This exercise concerns grammars for very simple languages.

\renewcommand{\labelenumi}{\alph{enumi}.}
\begin{enumerate}
\item Write a context-free grammar for the language \textit{$a^nb^n$}.
\item Write a context-free grammar for the palindrome language: the
  set of all strings second half is the reverse of the first half.
\end{enumerate}


A context-free grammar is a 4-tuple: $(V,\sum,R,S)$ where

\begin{tabular}{l l}
  {V}      & {set of variables}\\
  {$\sum$} & {alphabet of terminals}\\
  {R}      & {set of productions/rewrite rules}\\
  {S}      & {start symbol}\\
\end{tabular}

\begin{description}
\item [Answer a] Context-free grammar for the language $a^nb^n$
  
  \begin{tabular}{l c l}
    {V}      & {=}             & {\{a,b\}}\\
    {$\sum$} & {=}             & {S}\\
    {R}      & {=}             & {$S \rightarrow \varepsilon$}\\
    {S}      & {$\rightarrow$} & {aSb}\\
  \end{tabular}

  This results in $S \rightarrow aSb | \varepsilon$ since we,
  probably, want it to hold for $n \geq 0$.
\item [Answer b] Context-free grammar for the palindrome language.

  \begin{tabular}{l c l}
    {V}      & {=}             & {\{a,b,c\}}\\
    {$\sum$} & {=}             & {S}\\
    {R}      & {=}             & {$S \rightarrow \varepsilon$}\\
    {S}      & {$\rightarrow$} & {$a | b | c$}\\
    {S}      & {$\rightarrow$} & {$aSa | bSb | cSc$}\\
  \end{tabular}
  
  \textbf{Basis:} $\varepsilon$, a, b and c are
  palindromes.\\
  \textbf{Induction:} If S is a palindrome, the aSa, bSb and
  cSc are also palindromes.
\end{description}

Therefore the answer is $S \rightarrow \varepsilon|a|b|c|aSa|bSb|cSc$

\subsection{Answer 3}

\begin{center}
  \begin{tabular}{| p{5cm} | p{5cm} |}
    \hline
    {\textbf{Scrambled text}} & {\textbf{Unscrambled text}}\\
    \hline
    {have programming a seen never I language better} &
    {I have never seen a better programming language}\\
    \hline
    {loves john mary} &
    {john loves mary OR mary loves john} \\
    \hline
    {is the communication exchange of intentional
     information brought by about the production perception of and signs
     from drawn a of system signs conventional shared} &
    {communication is the intentional exchange of information
     brought about by the production and perception of signs drawn
     from a shared system of conventional signs}\\
    \hline
  \end{tabular}
\end{center}

The first two text are quite easy to unscramble, but the third one is
harder. The unscrambled text can be found in the second paragraph,
right at the beginning of chapter 22 in the book. 

To have a machine unscramble the strings of word we could train a
n-gram on a training corpus, POS-tag the words and put them in a
Markow chain with probabilities between all pairs. After that we could
run an EM-algorithm over it to extract the highest probable
permutation.
